#参考https://blog.csdn.net/jayshon_jaa/article/details/83040821

import copy
import time
import sys
t1=time.time()
#待求解的数独，未知的用0表示
solve = [[0, 0, 0, 0, 0, 0, 0, 0, 0],
          [9, 4, 3, 6, 8, 2, 1, 7, 5],
          [6, 7, 5, 0, 0, 1, 2, 8, 3],
          [1, 5, 4, 2, 3, 7, 8, 9, 6],
          [3, 6, 9, 8, 4, 5, 7, 2, 1],
          [2, 8, 7, 1, 6, 9, 5, 3, 4],
          [5, 2, 1, 9, 7, 4, 3, 6, 8],
          [4, 3, 8, 5, 2, 6, 9, 1, 7],
          [7, 9, 6, 3, 1, 8, 4, 5, 0]]

class sudoku:
    # 输出每一次调试的结果
    def debug(self):
        for list in solve:
            print(list)
        print("\n")

    # 检查重复,如果有重复，返回1；无重复，返回0
    def check_repetition(self,list):
        flag=0
        for i in range(1,10):
            if list.count(i)>=2:
                return 1
            else:
                flag=flag+1
        if flag==9:
            return 0

    # 检查横向重复
    def check_row(self,row):
        list = solve[row]  # 横向
        r1 = self.check_repetition(list)
        if r1 == 0:
            return 0
        else :
            return 1

    # 检查纵向重复
    def check_column(self,column):
        list = []  # 纵向
        for num in solve:
            list.append(num[column])
        r2 = self.check_repetition(list)
        if r2==0:
            return 0
        else:
            return 1

    # 检查对应的每个九宫格有无重复值
    def check_square(self,x,y):
        x,y=y,x
        if x>=9 or y>=9:
            return
        # 将待求解的数组分割并放入square中
        square = []
        for i in range(0+y//3*3, 3+y//3*3):
            for j in range(0+x//3*3, 3+x//3*3):
                square.append(solve[i][j])
        # 检查square中9个数有无重复
        r3 = self.check_repetition(square)
        if r3==0:
            return 0
        else:
            return 1

    # 检查重复并将是否有重复的结果返回，无重复则返回0
    def check(self,x,y):
        r1 = self.check_row(x)
        r2 = self.check_column(y)
        r3 = self.check_square(x, y)
        result=r1+r2+r3
        return result

    # 获得下一个空值，返回row,column值，当没有0时，退出
    def get_next(self):
        i = 0
        for list in solve:
            try:  # 当0不在列表中时，跳过
                column = list.index(0) #找到0所在的位置
                row = solve.index(list)
                res = (row, column)
                return res
            except ValueError:
                i = i + 1
                if i == 9:
                    t2=time.time()
                    print("总用时={}".format(t2 - t1))
                    sys.exit()

    # 位置修正，传入的坐标的下一个值，需换行时列清零
    def coordinate(self,row, column):
        if row == 0 and column == -1:
            return
        if row == 8 and column == 9:
            return
        if column == -1:
            column = 8
            row = row - 1
        if column == 9:
            column = 0
            row = row - 1
        return (row, column)

    # 获得上一个已填值的行、列位置
    def get_last(self,row, column):
        solve[row].insert(column, 0)
        solve[row].pop(column + 1)
        column = column - 1
        row, column = self.coordinate(row, column)#位置修正
        r = solve[row][column] * compare[row][column]
        while r != 0:
            column = column - 1
            row, column = self.coordinate(row, column)
            r = solve[row][column] * compare[row][column]
        return (row, column)

    #穷举,并调用检查的函数以及debug函数
    def blank(self):
        try:
            row, column=self.get_next()
        except TypeError:#已填完
            exit(0)
        j=0
        flag=0
        for i in range(1,10):
            solve[row].insert(column,i)
            solve[row].pop(column+1)
            self.debug()
            r = self.check(row, column)
            if r==0:#无重复值
                return
            else:
                j = j + 1
                if j==9:
                    flag=1
                    break
        #当发现在一处填入1到9均不符合时，返回上一个填写的值进行更改
        if flag==1:
            row, column = self.get_last(row, column)
            value=solve[row][column]
            self.debug()
            while value == 9:
                row, column = self.get_last(row, column)
                value = solve[row][column]
                self.debug()
            while value<9:
                for k in range(value+1,10):
                    solve[row].insert(column, k)
                    solve[row].pop(column + 1)
                    self.debug()
                    r=self.check(row,column)
                    if r!=0:#有重复
                        if k==9:
                            row, column = self.get_last(row, column)
                            value=solve[row][column]
                            self.debug()
                            while value==9:
                                row, column = self.get_last(row, column)
                                value = solve[row][column]
                                self.debug()
                            break
                    else:
                        return

if __name__=="__main__":
    compare = copy.deepcopy(solve)
    sudoku = sudoku()
    while 1:
        sudoku.blank()
